package com.sheng.leetcode.year2025.month09.day10;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author by ls
 * @date 2025/9/16
 * <p>
 * 1733. 需要教语言的最少人数<p>
 * <p>
 * 在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。<p>
 * 给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：<p>
 * 总共有 n 种语言，编号从 1 到 n 。<p>
 * languages[i] 是第 i 位用户掌握的语言集合。<p>
 * friendships[i] = [ui, vi] 表示 ui 和 vi 为好友关系。<p>
 * 你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。<p>
 * 请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]<p>
 * 输出：1<p>
 * 解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]<p>
 * 输出：2<p>
 * 解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。<p>
 * <p>
 * 提示：<p>
 * 2 <= n <= 500<p>
 * languages.length == m<p>
 * 1 <= m <= 500<p>
 * 1 <= languages[i].length <= n<p>
 * 1 <= languages[i][j] <= n<p>
 * 1 <= ui < vi <= languages.length<p>
 * 1 <= friendships.length <= 500<p>
 * 所有的好友关系 (ui, vi) 都是唯一的。<p>
 * languages[i] 中包含的值互不相同。<p>
 */
public class LeetCode1733 {

    @Test
    public void test() {
//        int n = 2;
//        int[][] languages = {{1}, {2}, {1, 2}}, friendships = {{1, 2}, {1, 3}, {2, 3}};
        int n = 3;
        int[][] languages = {{2}, {1, 3}, {1, 2}, {3}}, friendships = {{1, 4}, {1, 2}, {3, 4}, {2, 3}};
        System.out.println(new Solution().minimumTeachings(n, languages, friendships));
    }
}

class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.length;
        // 要求 friendships 内的朋友们至少有一门语言是能够满足互相沟通的
        // 可以选择一门语言进行教学，要求获取学习人数最少的
        // learned[i][x] 标识第 i 个人是否精通 x 语言
        boolean[][] learned = new boolean[m][n + 1];
        for (int i = 0; i < m; i++) {
            for (int x : languages[i]) {
                learned[i][x] = true;
            }
        }

        // 用于保存无法互相沟通需要学习语言的好朋友
        List<int[]> todoList = new ArrayList<>();
        next:
        // 循环好朋友
        for (int[] f : friendships) {
            int u = f[0] - 1, v = f[1] - 1; // 减一，下标从 0 开始
            // 循环好朋友 u 所会的语言
            for (int x : languages[u]) {
                // 判断好朋友 v 是否也会 x 语言
                if (learned[v][x]) {
                    // 如果会，则结束这一次循环
                    continue next;
                }
            }
            // 好朋友有沟通障碍，则将这一对好朋友加入 todoList 集合中
            todoList.add(f);
        }

        // 将人数赋予 ans(需要学习语言的人数)
        int ans = m;
        // 枚举需要教的语言 k
        for (int k = 1; k <= n; k++) {
            Set<Integer> set = new HashSet<>();
            for (int[] f : todoList) {
                int u = f[0] - 1, v = f[1] - 1;
                // u 需要学习语言 k
                if (!learned[u][k]) {
                    set.add(u);
                }
                // v 需要学习语言 k
                if (!learned[v][k]) {
                    set.add(v);
                }
            }
            // set.size() 是需要学习语言 k 的人数
            ans = Math.min(ans, set.size());
        }
        return ans;
    }
}
